package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC_386_LexicographicalNumbers {

    public static void main(String[] args) {

    }

    class Solution {
        public List<Integer> lexicalOrder(int n) {
            int c = 0;
            int t = n;
            while (t > 0) {
                c++;
                t = t / 10;
            }
            ArrayList<Integer> result = new ArrayList<>();
            char[] num = new char[c];
            helper(num, 0, n, result);
            return result;
        }

        void helper(char[] num, int i, int max, ArrayList<Integer> result) {
            if (i == num.length) {
                int val = convert(num);
                if (val <= max)
                    result.add(val);
                return;
            }
            if (i == 0) {
                for (char c = '1'; c <= '9'; c++) {
                    num[i] = c;
                    helper(num, i + 1, max, result);
                }
            } else {
                num[i] = 'a';
                helper(num, num.length, max, result);
                for (char c = '0'; c <= '9'; c++) {
                    num[i] = c;
                    helper(num, i + 1, max, result);
                }
            }
        }

        private int convert(char[] arr) {
            int result = 0;
            for (char anArr : arr) {
                if (anArr >= '0' && anArr <= '9')
                    result = result * 10 + anArr - '0';
                else
                    break;
            }
            return result;
        }

    }
}